package com.zp.self.module.level_4_算法练习.数据结构.String;

import com.google.common.collect.Lists;

import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_139_单词拆分 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_139_单词拆分().wordBreak("leetcode", Lists.newArrayList("leet","lee", "code")));
    }

    /**
    题目：给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

     注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

     示例 1：
     输入: s = "leetcode", wordDict = ["leet", "code"]
     输出: true
     解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

     示例 2：
     输入: s = "applepenapple", wordDict = ["apple", "pen"]
     输出: true
     解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
          注意，你可以重复使用字典中的单词。

     示例 3：
     输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
     输出: false

    分析：【P 💜💜💜💜】
       1.递归：右移下标找到匹配单词，剩余部分继续递归匹配
               如果当前匹配的串失败了，则右移动下标，继续找匹配的单词，剩余部分继续递归
                --【超时了】
             优化：加个数组记录失败下标，【很动态规划】干(oﾟvﾟ)ノ
            --执行用时：1 ms, 在所有 Java 提交中击败了99.66%的用户

    边界值 & 注意点：
       1.
     **/
    public boolean wordBreak(String s, List<String> wordDict) {
        //找到wordDict的最大长度，当匹配串大于最大单词长度时，可提前返回false
        int maxLen=0;
        for (String s1 : wordDict)
            maxLen = Math.max(s1.length(),maxLen);
        boolean[] isOk = new boolean[s.length()];
        return dfs(s,0,wordDict,maxLen,isOk);
    }
    /**
     * Description: 递归3步曲：单步操作，返回值，终止条件
     * @param s 剩余的字符串
     * @param start 开始校验的下标
     * @param wordDict 单词集合
     * @param maxLen 最大长度
     * @param isOk 每个下标是否走过  true:表示走过且行不通
     */
    private boolean dfs(String s, int start, List<String> wordDict, int maxLen, boolean[] isOk) {
        if(start==s.length())return true;
        if(isOk[start])return false;
        for (int i = start+1; i <= s.length(); i++) {
            String currentStr = s.substring(start, i);
            if(wordDict.contains(currentStr)){
                boolean dfs = dfs(s, i, wordDict, maxLen, isOk);
                if(dfs)
                    return true;
                else
                    isOk[i]=true;
            }
            if(i-start>maxLen)return false;
        }
        return false;
    }
}
